10199 - Tourist guide/Intentando ayudar/ani_mitr86.cpp

   1 #include<cstdio>
   2 #include<map>
   3 #include<vector>
   4 #include<string>
   5 #include<algorithm>
   6 #include<iostream>
   7 using namespace std;
   8 //#include<conio.h>
   9
  10 void articulation_point_visit
  11 (vector<int> *list, int* d, int* low, int* child_cnt, int n, int& time){
  12    low[n]=d[n]=time++;
  13    int l=list[n].size();
  14    for(int v, i=0; i<l; i++){
  15       v=list[n][i];
  16       if(d[v]==0){
  17          child_cnt[n]++;
  18          articulation_point_visit(list, d, low, child_cnt, v, time);
  19          low[n]<?=low[v];
  20       }
  21       else low[n]<?=d[v];
  22    }
  23    return;
  24 }
  25
  26 vector<int> articulation_point(vector<int> *list, int sz){
  27    bool root[sz+1];
  28    int d[sz+1], low[sz+1], child_cnt[sz+1], time=1, l;
  29    for(int i=1; i<=sz; i++){ root[i]=false; d[i]=0; child_cnt[i]=0;}
  30    vector<int> points;
  31
  32    for(int i=1; i<=sz; i++) if(d[i]==0){
  33       root[i]=true;
  34       articulation_point_visit(list, d, low, child_cnt, i, time);
  35    }
  36    for(int i=1; i<=sz; i++){
  37       if(root[i]&&(child_cnt[i]>1)) points.push_back(i);
  38       if(!root[i]){
  39          l=list[i].size();
  40          for(int j=0; j<l; j++) if(d[i]<=low[list[i][j]]){ points.push_back(i); break;}
  41       }
  42    }
  43
  44    return points;
  45 }
  46
  47 int main(){
  48     //freopen("input.txt", "r", stdin);
  49    int n, r, cnt=1;
  50    string str, u, v;
  51    map<string, int> m;
  52    map<int, string> mi;
  53    vector<string> vec;
  54    vector<int> points;
  55    while(1){
  56       scanf("%d", &n);
  57       if(n==0) break;
  58       if(cnt>1) printf("\n");
  59       m.clear(); mi.clear(); vec.clear();
  60       for(int c=1, i=0; i<n; i++, c++){
  61          cin>>str;
  62          m[str]=c; mi[c]=str;
  63       }
  64       scanf("%d", &r);
  65       vector<int> list[n+1];
  66       for(int x, y, i=0; i<r; i++){
  67          cin>>u>>v;
  68          x=m[u]; y=m[v];
  69          list[x].push_back(y);
  70          list[y].push_back(x);
  71       }
  72       points=articulation_point(list, n);
  73       printf("City map #%d: %d camera(s) found\n", cnt++, points.size());
  74       for(vector<int>::iterator it=points.begin(); it!=points.end(); it++)
  75          vec.push_back(mi[*it]);
  76       sort(vec.begin(), vec.end());
  77       for(vector<string>::iterator it=vec.begin(); it!=vec.end(); it++) cout<<*it<<endl;
  78    }
  79    //getch();
  80    return 0;
  81 }